#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2021年02月26日
描    述：
Copyright (C) 2021 All rights reserved.
'''

n, m = map(int, input().split())

annex = dict()
main_iterm = dict()

for i in range(1, m + 1):
    x, y, z = map(int, input().split())  # 价格，重要性，是否主件
    if z == 0:  # 主件
        main_iterm[i] = [x, y]
    elif z in annex:
        annex[z].append([x, y])
    else:
        annex[z] = [[x, y]]

m = len(main_iterm)

v = [[]]
w = [[]]

dp = [[0] * (n+1) for _ in range(m + 1)]
for key in main_iterm:
    v_tmp = list() #价格
    w_tmp = list() #价格*重要性
    v_tmp.append(main_iterm[key][0])
    w_tmp.append(main_iterm[key][0] * main_iterm[key][1]) # 主件
    if key in annex:  # 存在附件
        v_tmp.append(v_tmp[0] + annex[key][0][0])
        w_tmp.append(w_tmp[0] + annex[key][0][0]*annex[key][0][1]) # 主件 + 附件1
        if len(annex[key]) > 1: #存在附件2
            v_tmp.append(v_tmp[0] + annex[key][1][0])
            w_tmp.append(w_tmp[0] + annex[key][1][0] * annex[key][1][1]) # # 主件 + 附件2

            v_tmp.append(v_tmp[1] + annex[key][1][0])
            w_tmp.append(w_tmp[1] + annex[key][1][0] * annex[key][1][1]) # # 主件 + 附件1 + 附件2
    v.append(v_tmp)
    w.append(w_tmp)

for i in range(1, m+1):
    #print(len(v[i]))
    for j in range(10, n+1, 10):
        max_i = dp[i-1][j]
        for k in range(len(v[i])):
            if j - v[i][k] >= 0:
                max_i = max(max_i, dp[i-1][j-v[i][k]] + w[i][k])

        dp[i][j] = max_i

print(dp[m][n])
